package heap;

import com.sun.xml.internal.bind.util.Which;

/**
 * @Author Zhouchb
 * @Create 2021-10-2021/10/28 :22:16
 * @Description
 */
class HeapTest{
    public static void main(String[] args) {
        Heap<String> heap = new Heap<String>(7);
        heap.insert("D");
        heap.insert("A");
        heap.insert("C");
        heap.insert("B");
        heap.insert("E");
        heap.insert("F");
        heap.insert("G");
        String result = null;
        while ((result=heap.delMax())!=null){
           System.out.println(result);
        }
    }
}
public class Heap<T extends Comparable<T>>{

    //用来存储元素的数组
    private T[] items;
    //记录堆中元素的个数
    private int N;

    //创建容量为capacity的Heap对象
    public Heap(int capacity){
        this.items = (T[]) new Comparable[capacity+1];
        this.N = 0;
    }
    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i,int j){
        return items[i].compareTo(items[j])<0;
    }
    //交换堆中i索引和j索引处的值
    private void exch(int i,int j){
        T temp;
        temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    //往堆中插入一个元素
    public void insert(T t){
        items[++N] = t;
        swim(N);
    }
    //使用上浮算法，使索引k处的元素才能在堆总处于一个正确的位置
    private void swim(int k){
        while (k>1){
            if (less(k/2,k)){
                exch(k/2,k);
            }else {
                break;
            }
            k=k/2;
        }
    }
    //删除堆中最大的元素，并返回这个最大元素
    public T delMax(){
        T max = items[1];
        exch(1,N);
        items[N] = null;
        N--;
        sink(1);
        return max;
    }
    //使用下沉算法，使缩影k处的元素能在堆中处于一个正确的位置
    private void sink(int k){
        int max;
        while (2*k<=N){
            if (2*k+1<=N){
                if (less(2*k+1,2*k)){
                    max=2*k;
                }else {
                    max=2*k+1;
                }
            }else {
                max=2*k;
            }
            //比较当前节点和较大子节点的值
            if (!less(k,max)){
            break;
            }
            //交换k索引处的值和max索引处的值
            exch(k,max);
            k=max;
        }
    }

}
